package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/find-the-duplicate-number/description/'>寻找重复数(Find the Duplicate Number)</a>
 * <p>给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。</p>
 * <p>假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。</p>
 * <p>你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,3,4,2,2]
 *      输出：2
 *
 * 示例 2：
 *      输入：nums = [3,1,3,4,2]
 *      输出：3
 *     </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= n <= 10^5</li>
 *         <li>nums.length == n + 1</li>
 *         <li>1 <= nums[i] <= n</li>
 *         <li>nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/30 13:49
 */
public class LC0287FindTheDuplicateNumber_M {

    static class Solution {

        public int findDuplicate(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                // 当前下标所对应的值。如果不等于下标+1
                /*
                    例如：1,3,4,2,2
                    ==>置换后变成：
                         1 2 3 4
                   index 0 1 2 3
                 */
                while (nums[i] != i + 1) {
                    if (nums[i] == nums[nums[i]- 1] ) {
                        return nums[i];
                    }
                    // 交换位置
                    swap(nums, i, nums[i] - 1);

                }
            }
            return -1;
        }

        private void swap(int[] ints, int i1, int i2) {
            int temp = ints[i1];
            ints[i1] = ints[i2];
            ints[i2] = temp;
        }


        public int findDuplicate2(int[] nums) {
            // 先设置慢指针 slow和快指针 fast，慢指针每次走一步，快指针每次走两步
            // 根据「Floyd 判圈算法」两个指针在有环的情况下一定会相遇
            int slow = 0;
            int fast = 0;
            do {
                slow = nums[slow];
                fast = nums[nums[fast]];
            } while (slow != fast);
            // 再将 slow放置起点 0，两个指针每次同时移动一步，相遇的点就是答案
            slow = 0;
            while (slow != fast) {
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findDuplicate(new int[]{1, 3, 4, 2, 1}));
        System.out.println(solution.findDuplicate(new int[]{3, 1, 3, 4, 2}));
        System.out.println(solution.findDuplicate(new int[]{2, 2, 2, 2, 2}));

    }
}
